In conventional networks, it may be desirable for layer 2 packet forwarding devices, such as bridges or switches, to be capable of interfacing with a variety of in-line processors. Yet many conventional in-line processors cannot process packet streams at the transmission rates typically employed by current high-speed networks. Therefore, conventional layer 2 packet forwarding devices typically divide high-speed packet streams of layer 2 packets into several lower-speed packet streams that are sent to several lower-speed in-line processors. In order to ensure that the low-speed substreams do not exceed the capacity of any individual in-line processor, the substreams may be load-shared using either software-based or hardware-based methods. Both conventional methods include receiving packets at a first transmission rate and forwarding them to a set of output ports of a transmission rate less than the first transmission rate.
Software-based methods for dividing streams of packets can include using hashing algorithms to divide high-speed packet streams by examining parameters within packets of an input packet stream. Typical software-based hashing algorithms utilize one or more bits included in the layer 2 and/or layer 3 fields of a packet, such as a portion of a media access control (MAC) address or an IP address, in order to generate a key (hash) and direct the packet to particular output port among a set of output ports. Generally, hashing algorithms employed in layer 2 packet forwarding devices extract information from the MAC address of a packet and perform a mathematical operation on the extracted information in order to generate a key that identifies the packet. Ideal hashing algorithms generate keys that uniquely identify each packet, while non-ideal hashing algorithms can generate a single key that identifies two or more packets. In such a case, a “collision” occurs and additional processing is required to identify the packet. In a layer 2 packet forwarding device using a software-based hashing algorithm to divide a packet stream, processing resources are dedicated to extracting information from each packet received and performing mathematical operations on the extracted information.
One problem with current layer 2 packet forwarding devices that use software-based hashing algorithms to divide packet streams is that these devices are not capable of dividing and load-balancing a high-speed packet stream into a set of output packet streams at wireline speeds. For example, a layer 2 packet forwarding device using a software-based hashing algorithm to divide a 10 Gb/sec input packet stream (received at a 10 Gb/sec input port) into 10×1 Gb/sec output packet streams (output to 10×1 Gb/sec output ports) could not divide the streams at the full 10 Gb/sec, without dropping packets. Moreover, imbalances in the output packet streams produced by the load-sharing algorithm would also result in dropped packets.
Hardware-based methods achieve wireline speeds by avoiding the mathematical operations performed by software-based hashing algorithms. Hardware-based methods typically divide and load-share a high-speed input packet stream into output packet streams by evenly dividing a portion of each packet's MAC address into the number of output streams. Typically, the 8 least significant bits of each packet's MAC address are used to divide layer 2 packet streams. The minimum number of bits examined must be sufficient to uniquely identify each output packet stream. For example, in Table 1 below, in order to divide a single input packet stream into 10 output packet streams, examination of at least 4 bits of a MAC address are required. The result is that 16 (i.e. 24) numbers must be reduced to 10 corresponding ports in order to evenly divide a packet stream into 10 output ports. If the resulting packet streams are not balanced, packets are dropped when all ports are under full load.
TABLE 112345678910000000010010001101000101011001111000100112345910111213141516100010011010101111001101111011115678910As illustrated in Table 1 above, the 16 possibilities generated as a consequence of expressing 10 in binary format cannot be evenly reduced to 10 output streams. The result is a set of unbalanced output packet streams resulting in dropped packets under the conditions described above. Thus, in order to maintain ideal load-sharing among output ports at wireline speeds, hardware-based methods require transmission capacities of the input and output ports equal powers of 2.
Thus, conventional packet forwarding devices cannot divide a stream of layer 2 packets into multiple substreams at wireline speeds unless the number of substreams equals a power of 2. Accordingly, a need exists for improved methods, systems, and computer program products for rate-based distribution of layer 2 packets for in-line processing at a layer 2 packet forwarding device.